package fun.coding.leetcode;

public class RotateList {

	public static void main(String[] args) {
		RotateList instance = new RotateList();
		
		int[] a1 = {1, 2, 3, 4, 5};
		ListNode l1 = LeetCodeHelpers.buildLinkedList(a1);
		ListNode res = instance.rotateRight(l1, 2);
		LeetCodeHelpers.printList(res);
	}
	/**
	 * 首先从head开始跑，直到最后一个节点，这时可以得出链表长度len。
	 * 然后将尾指针指向头指针，将整个圈连起来，接着往前跑len – k%len，从这里断开，就是要求的结果了。
	 * 
	 */
	public ListNode rotateRight(ListNode head, int n) {
		if (head == null || head.next == null) return head;
		
		int l = getListLength(head);
		
		int shift = l - n % l;
		if (shift == 0 || n % l == 0) return head;
		
		ListNode dummy = new ListNode(-1);
		dummy.next = head;
		ListNode cur = dummy;
		
		while (shift > 0) {
			cur = cur.next;
			shift--;
		}
		
		ListNode last = getLastNode(cur);
		dummy.next = cur.next;
		last.next = head;
		cur.next = null;
		
		return dummy.next;
	}
	
	public int getListLength(ListNode head) {
		int l = 0;
		
		while (head != null) {
			l++;
			head = head.next;
		}
		return l;
 	}
	
	public ListNode getLastNode(ListNode head) {
		while (head != null && head.next != null) {
			head = head.next;
		}
		return head;
	}
	/* use two pointers.
	 * 
	   public ListNode rotateRight(ListNode head, int n) {
	        if (head == null) {
	            return null;
	        }
	        
	        int length = getLength(head);
	        n = n % length;
	        
	        ListNode dummy = new ListNode(0);
	        dummy.next = head;
	        head = dummy;
	        
	        ListNode tail = dummy;
	        for (int i = 0; i < n; i++) {
	            head = head.next;
	        }
	      
	        // Used two pointers
	        while (head.next != null) {
	            tail = tail.next;
	            head = head.next;
	        }
	        
	        head.next = dummy.next;
	        dummy.next = tail.next;
	        tail.next = null;
	        return dummy.next;
	    }
	    */
}
